class RoadNode {
    node: cc.Vec2;
    f: number;
    g: number;
    cameFrom: cc.Vec2;

    constructor(node: cc.Vec2, f: number, g: number, cameFrom: cc.Vec2) {
        this.node = node;
        this.f = f;
        this.g = g;
        this.cameFrom = cameFrom;
    }
}

class PriorityQueue {
    public items: any[] = [];

    enqueue(item: any): void {
        let contain = false;
        for (let i = 0; i < this.items.length; i++) {
            if (this.items[i].f > item.f) {
                this.items.splice(i, 0, item);
                contain = true;
                break;
            }
        }

        if (!contain) {
            this.items.push(item);
        }
    }

    dequeue(): any {
        return this.items.shift();
    }

    isEmpty(): boolean {
        return this.items.length === 0;
    }
}
export default class MapUtil {
    //地图像素大小
    protected static _mapPixelSize: cc.Size = null;
    //地图锚点偏移量
    protected static _mapOffsetPoint: cc.Vec2 = null;
    //格子大小
    protected static _tileSize: cc.Size = new cc.Size(256, 128);
    //地图大小 宽高需要相同
    protected static _mapSize: cc.Size = new cc.Size(20, 20);

    //地图 (0, 0)点对应的像素坐标
    protected static _zeroPixelPoint: cc.Vec2 = cc.v2(0, 0);
    //划分区域的格子大小
    protected static _areaCellSize: cc.Size = null;
    protected static _areaSize: cc.Size = null;

    // 地图数据，这里假设是一个二维数组，需要根据您的地图数据来设置
    protected static _mapData: number[][] = [];

    constructor() {

    }
    public static initMapConfig(map: cc.TiledMap) {
        let uit = map.node;
        this._mapPixelSize = cc.size(uit.width, uit.height);

        this._mapOffsetPoint = cc.v2(uit.width * uit.anchorX, uit.height * uit.anchorY);
        this._tileSize = map.getTileSize();
        this._mapSize = map.getMapSize();
        this._mapPixelSize = cc.size(uit.width, uit.height);
        //console.log("map size", this._mapSize, "| _tileSize size",this._tileSize);

        this._zeroPixelPoint.x = this._mapSize.width * this._tileSize.width * 0.5;
        this._zeroPixelPoint.y = this._mapSize.height * this._tileSize.height - this._tileSize.height * 0.5;

        var vsize = cc.view.getVisibleSize();
        //划分区域的大小
        let showH: number = Math.min(Math.ceil(vsize.height / this._tileSize.height / 2) * 2 + 2, this._mapSize.height);
        this._areaCellSize = cc.size(showH, showH);
        this._areaSize = cc.size(Math.ceil(this._mapSize.width / showH), Math.ceil(this._mapSize.height / showH));

        this._mapData = [];
        // 遍历地图的每个图块
        for (let y = 0; y < this._mapSize.height; y++) {
            this._mapData[y] = [];
            for (let x = 0; x < this._mapSize.width; x++) {
                // 假设我们只有一个图块层，并且图层名为 "layer"
                // const tile = tiledMap.getLayer("layer").getTileAt(x, y);
                // if (tile) {
                //     // 假设不可走的图块 GID 为 1（需要根据您的图块集进行修改）
                //     this._mapData[y][x] = tile.getGID() === 1 ? 1 : 0;
                // } else {
                //     // 如果没有图块，我们认为它是可走的
                //     this._mapData[y][x] = 0;
                // }
                this._mapData[y][x] = 0; //暂定所有都可以行走
            }
        }
        console.log(this._mapData)

    }
    /**地图的像素大小*/
    public static get mapPixcelSize(): cc.Size {
        return this._mapPixelSize;
    }

    public static get mapSize(): cc.Size {
        return this._mapSize;
    }

    /**格子数量*/
    public static get mapCellCount(): number {
        return this._mapSize.width * this._mapSize.height;
    }

    /**每个区域包含的格子数量*/
    public static get areaCellSize(): cc.Size {
        return this._areaCellSize;
    }

    /**区域大小*/
    public static get areaSize(): cc.Size {
        return this._areaSize;
    }
    /**区域数量*/
    public static get areaCount(): number {
        return this._areaSize.width * this._areaSize.height;
    }

    /**获取格子id*/
    public static getIdByCellPoint(x: number, y: number): number {
        return x + y * this._mapSize.width;
    }

    /**获取格子坐标*/
    public static getCellPointById(id: number): cc.Vec2 {
        return cc.v2(id % this._mapSize.width, Math.floor(id / this._mapSize.width));
    }

    /**获取区域id*/
    public static getIdByAreaPoint(x: number, y: number): number {
        return x + y * this._areaSize.width;
    }

    /**获取区域坐标*/
    public static getAreaPointById(id: number): cc.Vec2 {
        return cc.v2(id % this._areaSize.width, Math.floor(id / this._areaSize.width));
    }

    // 世界像素坐标转地图坐标
    public static worldPixelToMapCellPoint(point: cc.Vec2): cc.Vec2 {
        //  转换原理 
        //  tiledMap 45度地图是已上方为(0,0)点 以左上方边界为y轴 右上方边界为x轴的坐标系
        //  所以只需要将点击坐标点的平行映射到地图坐标系的边界上 求解出映射点的像素坐标 / 格子大小 即可计算出对饮的 格子坐标
        let x: number = Math.floor(0.5 * this._mapSize.height + point.x / this._tileSize.width - point.y / this._tileSize.height);
        let y: number = Math.floor(1.5 * this._mapSize.width - point.x / this._tileSize.width - point.y / this._tileSize.height);
        return cc.v2(x, y);
    }

    //地图坐标(格子的中心点)转世界像素坐标
    public static mapCellToWorldPixelPoint(point: cc.Vec2): cc.Vec2 {
        let pixelX: number = this._zeroPixelPoint.x - (point.y - point.x) * this._tileSize.width * 0.5;
        let pixelY: number = this._zeroPixelPoint.y - (point.x + point.y) * this._tileSize.height * 0.5;
        return new cc.Vec2(pixelX, pixelY);
    }

    // 地图坐标转地图像素坐标
    public static mapCellToPixelPoint(point: cc.Vec2): cc.Vec2 {
        let worldPoint: cc.Vec2 = this.mapCellToWorldPixelPoint(point);
        return worldPoint.subtract(this._mapOffsetPoint);
    }

    //地图像素转地图坐标
    public static mapPixelToCellPoint(point: cc.Vec2): cc.Vec2 {
        let temp = point.clone();
        let worldPoint: cc.Vec2 = temp.add(this._mapOffsetPoint);
        return this.worldPixelToMapCellPoint(worldPoint);
    }

    // 获取邻居节点
    public static getNeighbors(node: cc.Vec2): cc.Vec2[] {
        const neighbors: cc.Vec2[] = [];
        const directions = [
            cc.v2(-1, 0), // 左
            cc.v2(1, 0),  // 右
            cc.v2(0, -1), // 上
            cc.v2(0, 1),  // 下
            cc.v2(-1, -1), // 左上
            cc.v2(1, -1),  // 右上
            cc.v2(-1, 1),  // 左下
            cc.v2(1, 1)   // 右下
        ];


        for (const dir of directions) {
            const neighbor = node.add(dir);
            //console.log("邻居节点：",neighbor,this.isWalkable(neighbor))
            if (this.isWalkable(neighbor)) {
                neighbors.push(neighbor);
            }
        }

        return neighbors;
    }

    // 判断节点是否可通过
    public static isWalkable(node: cc.Vec2): boolean {
        const x = Math.floor(node.x);
        const y = Math.floor(node.y);
        if (x < 0 || y < 0 || x >= this._mapSize.width || y >= this._mapSize.height) {
            return false;
        }
        return this._mapData[y][x] == 0;
    }

    // 计算启发式代价（曼哈顿距离）
    public static heuristic_cost_estimate(start: cc.Vec2, goal: cc.Vec2): number {
        return Math.abs(start.x - goal.x) + Math.abs(start.y - goal.y);
    }

    // A* 寻路算法
    // A* 寻路算法
    public static aStarSearch(start: cc.Vec2, goal: cc.Vec2): cc.Vec2[] {
        const startGrid = this.mapPixelToCellPoint(start);
        const goalGrid = this.mapPixelToCellPoint(goal);

        const openList: PriorityQueue = new PriorityQueue();
        const closedSet: Set<string> = new Set();
        const openListHashTable: Map<string, RoadNode> = new Map();

        const startNode = new RoadNode(startGrid, 0, 0, null);
        openList.enqueue(startNode);
        openListHashTable.set(startGrid.toString(), startNode);

        while (!openList.isEmpty()) {
            const current = openList.dequeue() as RoadNode;

            if (current.node.equals(goalGrid)) {
                const path: cc.Vec2[] = [];
                let temp: RoadNode = current;
                while (temp.cameFrom) {
                    path.push(temp.node);
                    temp = openListHashTable.get(temp.cameFrom.toString()) as RoadNode;
                }
                path.reverse();
                return path;
            }

            closedSet.add(current.node.toString());

            for (const neighbor of this.getNeighbors(current.node)) {
                if (closedSet.has(neighbor.toString())) {
                    continue;
                }

                const tentative_g_score = current.g + 1;

                const existing = openListHashTable.get(neighbor.toString());
                if (!existing || tentative_g_score < existing.g) {
                    const neighborNode = new RoadNode(neighbor, tentative_g_score + this.heuristic_cost_estimate(neighbor, goalGrid), tentative_g_score, current.node);
                    if (existing) {
                        openListHashTable.set(neighbor.toString(), neighborNode);
                    } else {
                        openList.enqueue(neighborNode);
                        openListHashTable.set(neighbor.toString(), neighborNode);
                    }
                }
            }
        }

        return [];
    }

    // 私有方法：执行 DFS 搜索
    private static getMoveRangeDFS(node: cc.Vec2, visited: Set<string>, maxDistance: number, moveRange: cc.Vec2[]): void {
        // 如果超出最大移动距离，或者节点已被访问，则停止搜索
        if (maxDistance < 0 || visited.has(node.toString())) {
            return;
        }

        // 标记当前节点为已访问
        visited.add(node.toString());

        // 将当前节点添加到可移动范围列表
        moveRange.push(node);

        // 递归搜索周围 8 个方向的节点
        const directions = [
            cc.v2(0, 1), // 上
            cc.v2(0, -1), // 下
            cc.v2(-1, 0), // 左
            cc.v2(1, 0),  // 右
            // cc.v2(-1, 1), // 左上
            // cc.v2(1, -1), // 右下
            // cc.v2(-1, -1), // 左下
            // cc.v2(1, 1)   // 右上
        ];

        for (const dir of directions) {
            const neighbor = node.add(dir);
            if (this.isWalkable(neighbor)) {
                this.getMoveRangeDFS(neighbor, visited, maxDistance - 1, moveRange);
            }
        }
    }

    // 获取节点周围可移动范围
    public static getMoveRange(node: cc.Vec2, maxDistance: number): cc.Vec2[] {
        const visited: Set<string> = new Set();
        const moveRange: cc.Vec2[] = [];

        // 从当前节点开始 DFS 搜索
        this.getMoveRangeDFS(node, visited, maxDistance, moveRange);

        // 返回可移动范围的节点列表
        return moveRange;
    }

}